import java.util.HashMap;
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class code1 {
//    力扣 150 链表的随机复制
public Node copyRandomList(Node head) {
    // 解法一：
    // 使用 hash 表来记录 旧结点 和 新创建的节点之间的映射关系
    // 通过循环首先将获取的节点信息记录到这个新的节点中

    // 首先判断当前节点为 null 的情况
    if(head == null) {
        return null;
    }

    // 首先创建一个指针指向当前需要复制的链表 head 处
    Node cur = head;
    // 创建一个 哈希表 这里面设置的参数都是 Node 类型的
    HashMap<Node, Node> map = new HashMap<>();

    // 此时复制各个节点，记录 旧节点 和 新节点 的映射关系
    while(cur != null) {
        Node NewCur = new Node(cur.val);
        map.put(cur, NewCur);
        // cur 指针后移动
        cur = cur.next;
    }
    // 循环一遍结束后，此时将 cur 重置到 head 处
    cur = head;

    // 在此针对新的节点进行 while 循环，通过 映射关系创建出新的返回链表
    while(cur != null) {
        // 重构整个链表的 next 指向
        map.get(cur).next = map.get(cur.next);
        // 重构整个链表的 ramdom 指向
        map.get(cur).random = map.get(cur.random);
        // 此时再将 cur 进行后移
        cur = cur.next;
    }
    // 最终返回新链表的 头 节点
    return map.get(head);
}
}
